package leetcode.primary;

import utils.tree.BinaryTree;
import utils.tree.TreeNode;

public class T105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return DFS(0,preorder.length-1,0,preorder.length-1,preorder,inorder);
    }

    /*
    * @param preLeft preRight 当前子树在当前递归的preorder中的左边界和右边界
    *@param inLeft inRight 当前子树在当前递归的inorder中的左边界和右边界
    * */
    public TreeNode DFS(int preLeft,int preRight,int inLeft,int inRight,int[] preorder,int[] inorder){
        if (preLeft>preRight || inLeft>inRight){
            return null;
        }
        TreeNode node = new TreeNode(preorder[preLeft],null,null);

        //找到root在inorder中对应的下标，左边的是左子树，右边的是右子树
        int rootIndex = getIndex(inorder, preorder[preLeft],inLeft,inRight);
        //左子树遍历序列的长度
        int lenLeft = rootIndex-inLeft;
        //右子树遍历序列的长度
        int lenRight = inRight-rootIndex;

        System.out.print(node.val+" ");
        System.out.print("左子树");
        System.out.println("rootIndex="+rootIndex+",preleft="+(preLeft+1)+",preright="+(lenLeft+preLeft)+",inleft="+inLeft+",inright="+(rootIndex-1));
        node.left = DFS(preLeft+1,lenLeft+preLeft,inLeft,rootIndex-1,preorder,inorder);
        System.out.print("右子树");
        System.out.println("rootIndex="+rootIndex+",preleft="+(lenLeft+preLeft+1)+",preright="+(preRight)+",inleft="+(rootIndex+1)+",inright="+(inRight));
        node.right = DFS(lenLeft+preLeft+1,preRight,rootIndex+1,inRight,preorder,inorder);
        return node;
    }

    public int getIndex(int[] nums,int key,int left,int right){
        for (int i = left; i <=right; i++) {
            if (nums[i]==key){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        T105 t105 = new T105();

        TreeNode root = t105.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        BinaryTree tree = new BinaryTree();
        tree.PostorderTravel(root);
    }
}
